package com.leetcode;

import java.util.HashMap;

public class LongestConsecutiveSequence {
	public int longestConsecutive(int[] num) {
		if (num.length == 0) return 0;
		
		HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
		int max = 1;
		for (int i : num) {
			if (map.containsKey(i)) continue;
			map.put(i, i);
			if (map.containsKey(i+1)) max = Math.max(max, merge(map, i, i+1));
			if (map.containsKey(i-1)) max = Math.max(max, merge(map, i-1, i));
		}
		return max;
    }
	
	private int merge(HashMap<Integer, Integer> map, int left, int right) {
		int lower = map.get(left);
		int upper = map.get(right);
		if (lower >= upper) return 0; // wrong case
		map.put(lower, upper);
		map.put(upper, lower);
		return upper-lower+1;
	}
}
